package src.greed;

import java.util.Arrays;

public class no135 {//分发糖果
    public static void main(String[] args) {
        int[] rate={1,2,87,87,87,2,1};
        System.out.println(candy(rate));
    }
    public static int candy(int[] ratings) {
        int n = ratings.length;
        int res=0;
//        for(int i=1;i<n;i++){
//            //由于要求最少的糖果，所以 i 处比左右都大时，只能+1，不能+2
//            if(ratings[i] != ratings[i-1]){
//                res++;
//            }
//        }

        //这种写法[1,2,87,87,87,2,1]的用例不符合，所有比旁边大的都是2，其实还有3、4、5个糖果的情况
//        int[] left = new int[n];//当前孩子和左边比的分差
//        left[0]=0;
//        int[] right = new int[n];//和右边孩子比的分差
//        right[n-1]=0;
//        for(int i=1;i<n;i++){
//            left[i]=ratings[i]-ratings[i-1];
//        }
//        for(int i=0;i<n-1;i++){
//            right[i]=ratings[1]-ratings[i+1];
//        }
//
//        for(int i=0;i<n;i++){
//            if(left[i]>0 ||right[i]>0){
//                res++;
//            }
//        }

        int[] candy=new int[n];
        Arrays.fill(candy,1);
        //先和左边孩子比
        for(int i=1;i<n;i++){
            if(ratings[i] > ratings[i-1]){
                candy[i]=candy[i-1]+1;
            }
        }
        //再和右边孩子比，必须倒序遍历
        for(int i=n-2;i>=0;i--){
            if(ratings[i]>ratings[i+1]){
                candy[i]=Math.max(candy[i+1]+1,candy[i]);
            }
        }
        for(int num:candy){
            res+=num;
        }

        return res;

    }
}
